class Solution:
    def minimumDistance(self, word: str) -> int:
        DP = [[0 for _ in range(26)] for _ in range(26)]
        max_range = 10 ** 5
        for i in range(26):
            x1, y1 = i // 6, i % 6
            for j in range(26):
                x2, y2 = j // 6, j % 6
                DP[i][j] = abs(x1 - x2) + abs(y1 - y2)
        st = [[0 for _ in range(26)] for _ in range(26)]
        for c in word:
            next_st = [[max_range for _ in range(26)] for _ in range(26)]
            index = ord(c) - ord('A')
            for i in range(26):
                for j in range(26):
                    if st[i][j] != max_range:
                        next_st[i][index] = min(next_st[i][index], st[i][j] + DP[j][index])
                        next_st[index][j] = min(next_st[index][j], st[i][j] + DP[i][index])
            st = next_st
        return min([min([st[i][j] for j in range(26)]) for i in range(26)])





data = Solution()
word = "CAKE"
print(data.minimumDistance(word))
